iT邦幫忙

2021 iThome 鐵人賽

DAY 7
0
自我挑戰組

每日攝取一點資料結構和演算法系列 第 7

Day7: [資料結構]Stack —堆疊和Queue— 佇列

  • 分享至 

  • xImage
  •  

https://ithelp.ithome.com.tw/upload/images/20210907/201286042Dd9oRst6r.jpg

Stack

Stack是一種資料結構,遵循著後進先出的原則,最晚放入堆疊的資料會被最先取出(LIFO Last-In-First-Out),最早放入堆疊的資料會被最後取出(FILO First-In-Last-Out),就像堆疊的盤子一樣,如果要添加盤子一定是從最上面開始放,如果要取出盤子也是從最上面開始拿,堆疊會有兩種操作,pop - 從上面移除和push - 從上面新增。

https://ithelp.ithome.com.tw/upload/images/20210907/2012860468rkH6Tnsy.png

用js實作Stack

class Stack {
    constructor(arr) {
        this.stack = arr;
    }
    push(item) {
        this.stack.push(item);
    }
    pop() {
        return this.stack.pop();
    }
    peek() {
        return this.stack[this.stack.length - 1];
    }
    size() {
        return this.stack.length;
    }
    print() {
        return this.stack;
    }
}

const stack = new Stack([2, 4, 9, 5, 8]);
stack.pop(); //8
stack.peek(); //5

stack.push(7);
stack.print(); //[2, 4, 9, 5, 7]

stack.size(); //5

Queue

https://ithelp.ithome.com.tw/upload/images/20210907/20128604pMA6Esw6hA.jpg
佇列可以把想像是一個排隊的隊伍,排在第一順位的客人買到了車票所以離開了隊伍,而隊伍的後方陸續有新的排隊人潮加入,和堆疊不同的是,佇列是先進先出(FIFO First-In-First-Out),跟堆疊的後進先出(LIFO Last-In-First-Out)是不一樣的,佇列有兩種操作,push - 從後面新增和shift - 從前面移除。

佇列跟array不同是沒有index

https://ithelp.ithome.com.tw/upload/images/20210907/20128604WkHUkx1zgj.png
左邊為queue,右邊為stack

用js實作Queue

class Queue {
    constructor(arr) {
        this.queue = arr;
    }
    push(item) {
        this.queue.push(item);
    }
    shift() {
        return this.queue.shift();
    }
    size() {
        return this.queue.length;
    }
    print() {
        return this.queue;
    }
}

const queue = new Queue([3, 6, 9, 1, 7]);
queue.shift(); //3

queue.push(2);
queue.print(); //[6, 9, 1, 7, 3]

queue.size(); //5

這時候眼尖的你應該發現,不管是Stack或是Queue,其實都可以用js的array方法, pop() 、push()、 shift()來實作。

理解了Stack和Queue之後,相信就會更清楚Event Loop的流程啦!相信大家都知道JavaScript是單線程的程式語言,一次只能做一件事情,所以Stack會把裡面的任務(由上而下)依序處理,每處理完一個片段就pop掉,直到Stack清空,這時queue如果還有排隊等候的任務就會加入到stack裡面,這個過程就是Event Loop。


圖片來源:https://medium.com/@Rahulx1/understanding-event-loop-call-stack-event-job-queue-in-javascript-63dcd2c71ecd


上一篇
Day6: [資料結構] -  Set
下一篇
Day8: [資料結構]Hash Table - 雜湊表
系列文
每日攝取一點資料結構和演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言